A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets. The packets are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Certain devices, referred to as routers, maintain routing information that describes routes through the network. A “route” can generally be defined as a path between two locations on the network. Conventional routers often maintain the routing information in the form of one or more routing tables or other data structures. The form and content of the routing tables often depend on the particular routing algorithm implemented by the router.
Upon receiving incoming packets, the routers examine information within the packets, and forward the packets in accordance with the routing information. In order to maintain an accurate representation of the topology of the network, routers periodically exchange routing information in accordance with routing protocols, such as the Border Gateway Protocol (BGP), the Intermediate System to Intermediate System (ISIS) protocol, the Open Shortest Path First (OSPF) protocol, and the Routing Information Protocol (RIP). The routers, for example, exchange control-plane messages conforming to the routing protocols to convey changes to routing topology.
Routing communications are very sensitive in nature. For example, by maliciously altering routing protocol communications between routers, or by masquerading as a router and outputting erroneous routing protocol communications, an attacker can cause a network to entirely misroute traffic, thereby severely disrupting network communications. Moreover, by intercepting routing communications, an attacker may assemble an understanding of a topology of the network and exploit the information in subsequent attacks.
Initial techniques for deterring such malicious behavior have proved very limited. For example, some techniques use simply authentication techniques (e.g., text-based passwords, MD5) between routers. Such techniques have proven to be weak and very susceptible to hacker attacks.